package leetcode.Over_Four_hundred;

import java.util.Arrays;
import java.util.Comparator;

public class Test435无重叠区间 {


    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    /**
     *
     * @param intervals
     * @return 需要移除的区间数
     */
    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        // 按照区间 end 值排序。每次选择结尾最小，并且和前一个区间不重叠的区间。
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.end - o2.end;
            }
        });
        int cnt = 0;
        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            //
            if (intervals[i].start < end) {
                continue;
            }
            // 没有重叠时，修正 end 的数据，计数器加 1
            end = intervals[i].end;
            cnt++;
        }
        // 用全部的区间数 - 没有重叠的区间数 = 和别人重叠的区间
        return intervals.length - 1 - cnt;
    }
}
